1. Field of the Invention
This invention relates generally to barcodes and, more particularly, to a method and computer program product for overcoming the inaccuracies inherent in a low-resolution line scan camera to correctly decode a barcode.
2. Background of the Invention
Barcodes have become a common part of the automatic recognition technology that enables a computer to accurately input information. There are a number of barcode schemes that have been devised for use in different industries and/or locations, and each scheme has its own rules.
For example, European Article Numbering (EAN) is the code most commonly used for numbering retail products in Europe. This code is entirely numeric, using only characters 0-9 and requiring two bars and two spaces to encode a single character. The coding itself is fairly complex, but has either thirteen or 8 digits, used as follows: country code (2-3 digits), manufacturer identification number (4-5 digits), product identification number (5 digits), and a one-digit check digit, which is required to be sure the barcode is correctly decoded. The Universal Product Code (UPC) used in the U.S. is a subset of EAN.
Other barcode systems include International Standard Book Numbering (ISBN), a subset of EAN used for books and ITF, a bar code that was developed for bulk packaging situations because EAN rules were not tolerant enough of print variations.
Code 39 is an alphanumeric barcode that was designed to eliminate the need for a check digit by making each character self-checking. The basic Code 39 contains the characters 0-9, A-Z, and-the symbols xe2x88x92, ., $, /, +, %, with xe2x80x9c*xe2x80x9d generally used as a start and stop character; an extended Code 39 set is also available, containing the entire ASCII character set.
The scheme for barcode 39 is illustrated in FIG. 1A. Barcode 100 represents the character string *123ABC*, as is shown below the barcode itself. For convenience of the reader in understanding, an equally spaced grid has been placed across the top of barcode 100 and a shaded area has been placed in the grid to mark divisions between characters. In code 39, nine elements are necessary for each characterxe2x80x94five lines and four spaces, with a narrow space between characters. Each space or bar has one of two widths, with wide elements being twice as wide as the narrow elements. Of the nine elements in each character, three elements will be wide, the others narrow. FIG. 1B is a table showing the barcode representation of the basic Code 39 character set. Notably, all numbers, letters, and the characters xe2x80x9cxe2x88x92xe2x80x9d, xe2x80x9c.xe2x80x9d, xe2x80x9c xe2x80x9d (space), and xe2x80x9c*xe2x80x9d are coded by two wide bars and three narrow bars, with variations in the location of the one wide space. In the extended code, other variations within the 3 of 9 coding are added, such as two wide spaces, or three wide bars.
To be maximally efficient, a barcode must be read and decoded in a very short time. Whether the applications use a high-resolution camera for processing thousands of parcels an hour or a low-resolution camera to scan an item every few seconds, it is important to quickly read and decipher a code that may not be clearly reproduced.
FIGS. 2A and 2B show examples of pictures of barcodes made using a low-resolution line scan camera. Each of these drawings represents a small number of scan lines, with the apparent height of the barcode being stretched for improved visualization. The nature of the camera results in graininess of the picture and allows a large amount of noise (most clearly shown in FIG. 2A) and distortion (most clearly shown in FIG. 2B), with the distortion being especially noticeable in the narrow bars of a barcode. Since the picture is not very precise, software is an important component in reading the barcode.
One method of decoding a barcode is disclosed in U.S. Pat. No. 5,748,804, which is hereby incorporated by reference. In this patent, a low-resolution image is processed to produce a trace of the intensity of pixels across the barcode, such as the trace in FIG. 3A. Through scaling operations explained more fully in the patent, the peaks and valleys that do not span the full dynamic range of the signal are stretched to the limits of the dynamic range, producing a trace like that shown in FIG. 3B. Using the latter trace, the area of each region that is bounded by the dynamic limits and the signal is calculated, with areas 310, 312, 314 representing bars and areas 311, 313, 315 representing spaces. The widths of the bars and spaces in the barcode are calculated from the corresponding measured areas.
It has been difficult to find a reliable program that will consistently and correctly read barcodes that have been read by a low-resolution line-scan camera. It has been very desirable, therefore, to find a method of decoding barcodes that is more reliable with low-resolution cameras.
The inventor has discovered that the prior difficulties in reading a line-scanned barcode are caused by manipulating and decoding the barcode as a single entity. A novel method is presented that looks at one character of the barcode at a time. The method is described for barcodes based on Code 39, and uses the known structure of the barcode to reset a threshold value between wide and narrow bars for each character. A software filter is used to create a window that only xe2x80x9cseesxe2x80x9d one character at a time. A determination is made of the width W of the widest bar in the window. Based on this width W, a threshold T is set to 75% of W to distinguish between narrow and wide bars. Once each bar in the window is defined as narrow or wide, a determination is made whether the content of this window meets the coding scheme. Notably, if the application uses only the basic code 39 set without the xe2x80x9c$xe2x80x9d, xe2x80x9c/xe2x80x9d, xe2x80x9c+xe2x80x9d or xe2x80x9c%xe2x80x9d, the coding scheme can be identified as having three narrow bars and two wide bars. If the window doesn""t meet the coding scheme, the first xe2x80x9cbarxe2x80x9d is presumed to be an error, the window is moved to locate the next bar, and the process resumes with determining the widest bar in the window. If the window does meet the coding scheme, a character is decoded from the pattern in the window and stored as the next character in a decoded label. For each decoded and stored character, the window is incremented to the next character, i.e., it moves to the next five bars and again resumes with determining the widest bar in the window. Further refinements include checking to see if the valid character is a start/stop character. If so, the width of the entire character is determined and used to double check successive characters, ensuring that they are the correct width. The decoded label is check to ensure that it is completely decoded before the process can end. The fact that the threshold is recalculated for each succeeding window provides great flexibility in reading a wide range of barcodes.